package com.algrithom.stack.monotonousstack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution2 {
    
    public static void main(String[] args){
        int[] num1 = {4,1,2};
        int[] num2 = {1,3,4,2};
        Solution2 solution2 = new Solution2();
        System.out.println(Arrays.toString(solution2.nextGreaterElement(num1,num2)));
    }
    
    public int[] nextGreaterElement(int[] nums1,int[] nums2){
        int[] result = new int[nums1.length];
        Arrays.fill(result,-1);
        Stack<Integer> stk = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>(0);
        for (int index = nums2.length - 1; index >= 0; index--) {
            while (!stk.empty() && stk.peek() <= nums2[index]) {
                stk.pop();
            }
            map.put(nums2[index],stk.isEmpty() ? -1 : stk.peek());
            stk.push(nums2[index]);
        }
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                result[i] = map.get(nums1[i]);
            }
        }
        return result;
    }
}
